The architectures of peripheral data storage systems have become increasingly varied and sophisticated. However, in order to allow data exchanges with a wide variety of host computational systems, many data storage systems store data substantially differently from the architectural appearance that is presented to a host computational system. These data storage systems emulate simpler data storage system architectures which a wide variety of host systems and host system administration personnel can readily understand and manipulate. To accomplish this, such data storage systems, generally referred to as "mapped data storage systems," provide or store at least one map or table for mapping blocks of data between their physical locations on the backing store of the data storage system and the logical address locations perceived by the host systems. In particular, for a backing store having disk storage devices, such mappings translate between the logical address scheme (which typically includes a logical device identification and a logical data address for locations within the logical device) used by a host computational system and the physical addressing scheme (which typically includes cylinder track and sector locations) used by the backing store as is well known in the art. Thus, for a host to access data on a mapped data storage system, the host system provides the mapped data storage system with the logical address of the data, the mapped data storage system then uses a mapping table to look up the physical storage location corresponding to the logical address and subsequently locates the data and transfers it to the host.
As a further enhancement, some data storage systems, known as "dynamically mapped data storage systems," do not require that the mapping between logical and physical addresses be fixed. That is, a dynamically mapped data storage system can relocate data on the backing store transparently to the activities of any host system. This feature allows the data storage system, for example, to efficiently store variable length data resulting from data compaction techniques, since fragmentation of the backing store can be alleviated by relocating stored data such that unallocated storage fragments can be coalesced. Thus, as the physical address where a data item is stored varies, the stored mapping associating logical and physical addresses is modified.
In yet another, departure from the data storage architecture perceived by a host system, it is also common practice for mapped data storage systems to provide a data caching mechanism such that frequently referenced data can be transferred at electronic speeds to and from a host system. Such a cache typically becomes the data storage system interface between the backing store and the host system. Therefore, all host system input and output to the data storage system, at least temporarily, resides in the cache memory and the cache or a related controller is responsible for both staging data (i.e., reading data from the backing store into the cache memory) and destaging data (i.e., writing data from the cache memory to the backing store). Moreover, it is known that as a cache memory increases in size, there is an increased likelihood of the requested data being in the cache and, thus, faster data transfers occur between a host computational system and the data storage system. It is also known that as a cache memory increases in size, the proportion of data stages over data destages decreases substantially. This is due to the facts that: (i) in general, a substantial majority of the data transfer activity between a host computational system and a data storage system is directed at only a small percentage of the data. Therefore, by having a sufficiently large cache memory, a substantial portion of the most active data can remain in the cache memory without restaging, and (ii) regardless of the cache memory size, to assure data persistence and integrity, destaging operations are periodically required for modified data residing in the cache memory. Thus, since many mapped data storage systems can have large cache memories, data destages become a significant bottleneck to increasing overall sustained data transfer rates with host systems.
It would, therefore, be advantageous to substantially speed up the destaging process without substantially decreasing the overall efficiency of a dynamically mapped data storage system. The present invention is intended to attain this advantage by substantially decreasing the time taken in locating and writing to unallocated storage area(s) on the backing store where data is to be destaged.